\documentclass[C:/Users/12748/Desktop/latex模板/main/main.tex]{subfiles}
\begin{document}

$CDQ$分治是离线的动态算法，会付出$log$的代价。只考虑左区间修改对右区间查询的影响。第一维排序，第二维归并，第三维树状数组。

例题：三维偏序问题。$a_i \leq a_j \;,\; b_i \leq b_j \;,\; c_i \leq c_j , i \neq j$的二元组$(i,j)$个数。

做法：$ans[i]$表示比$(a_i , b_i , c_i)$小的个数。每个三元组相当于是一个修改操作和一个查询操作。我们先按照$a_i$升序，然后$a_i$就变成了操作下标，然后把每个三元组拆成修改操作和查询操作，排序时如果$a_i$相同，修改操作在查询操作之前。$solve(l , r)$是对$b_i$降序，然后用$[l , mid]$的操作向树状数组里插$c_i$的值，用$[mid + 1 , r]$的操作去询问。

\begin{lstlisting}
int n , k ;
int ans[maxn] , num[maxn] ;
struct node
{
	bool op ;
	int a , b , c ;
	int id , cur ;
} q[maxn << 1] ;
bool cmp1(node s , node t)
{
	if(s.a == t.a)  return s.op < t.op ;
	else  return s.a < t.a ;
}
bool cmp2(node s , node t)
{
	if(s.b == t.b)  return s.op < t.op ;
	else  return s.b < t.b ;
}
struct BIT
{
	int tree[maxm] ; 
	void init()
	{
		mem0(tree) ;
	}
	int lowbit(int k)
	{
		return k & -k;
	}
	void add(int n , int x , int k)
	{
		while(x <= n)
		{
			tree[x] += k ;
			x += lowbit(x) ;
		}
	}
	int sum(int x)  // sum[l , r] = sum(r) - sum(l - 1)
	{
		int ans = 0 ;
		while(x != 0)
		{
			ans += tree[x] ;
			x -= lowbit(x) ;
		}
		return ans ;
	}
	int query(int l , int r)
	{
		return sum(r) - sum(l - 1) ;
	}
} bit ;
void solve(int l , int r)
{
	if(l == r)  return ;
	int mid = (l + r) / 2 ;
	solve(l , mid) ;
	solve(mid + 1 , r) ; 
	sort(q + l , q + r + 1 , cmp2) ; // 如果打乱了顺序，那就只能后序遍历。
	rep(i , l , r)  
	if(q[i].op == 0 && q[i].id <= mid)  bit.add(k , q[i].c , 1) ;
	else if(q[i].op == 1 && q[i].id > mid)  ans[q[i].cur] += bit.query(1 , q[i].c) ; 
	rep(i , l , r)  
	if(q[i].op == 0 && q[i].id <= mid)  bit.add(k , q[i].c , -1) ; 	
}
int main()
{
	rr(n , k) ;
	rep(i , 1 , n)
	{
		rr(q[i].a , q[i].b) , r(q[i].c) ;
		q[i].op = 0 , q[i].cur = i ;
		q[i + n].a = q[i].a ;
		q[i + n].b = q[i].b ;
		q[i + n].c = q[i].c ;
		q[i + n].op = 1 , q[i + n].cur = i ;
	}
	sort(q + 1 , q + n * 2 + 1 , cmp1) ;
	rep(i , 1 , n * 2)  q[i].id = i ;
	mem0(ans) ;
	bit.init() ;
	solve(1 , n * 2) ;
	rep(i , 1 , n)  ans[i] -- ;
	return 0 ;
}


\end{lstlisting}
\end{document}


